package hot

/**
原题链接:
https://leetcode.cn/problems/sort-list/description/

148. 排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：
输入：head = []
输出：[]
*/

type ListNode struct {
	Val  int
	Next *ListNode
}

func sortList(head *ListNode) *ListNode {
	//1.如果头节点或者头节点的后续节点为nil,直接返回即可
	if head == nil || head.Next == nil {
		return head
	}

	//2.快慢指针来寻找中点
	fast := head.Next
	slow := head

	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}

	tmp := slow.Next                  //中点的下一个节点
	slow.Next = nil                   //打断链表
	left := sortList(head)            //前半段的头节点, 依然是head, 递归调用
	right := sortList(tmp)            //后半段的头结点, 是tmp, 递归调用
	curNode := &ListNode{}            //临时head, 在循环中不停后移
	res := curNode                    //第一个元素,它是不变的, 不参与排序, 它的下一个真正的 head
	for left != nil && right != nil { //两个有序链表合并
		if left.Val < right.Val {
			curNode.Next = left
			left = left.Next
		} else {
			curNode.Next = right
			right = right.Next
		}
		curNode = curNode.Next
	}

	//必有一个链表移动到了末尾
	if left != nil {
		curNode.Next = left
	} else {
		curNode.Next = right
	}

	return res.Next
}
